class Solution:
	# @param s, a string
	# @return an integer
	def numDecodings(self, s):
		n = len(s)
		if n == 0 or s[0] == '0':
			return 0
		dp = [1,1]
		for i in xrange(1, len(s)):
			a = int(s[i-1])
			b = int(s[i])
			if a == 0 and b == 0:
				return 0
			if b == 0:
				if a >= 3:
					return 0
				else:
					dp.append(dp[-2])
			elif a*10+b > 10 and a*10+b <=26:
				dp.append(dp[-1] + dp[-2])
			else:
				dp.append(dp[-1])
		return dp[-1]

if __name__ == '__main__':
	so = Solution()
	print(so.numDecodings("11011"))

